package com.zjsru.plan2025.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 2537. 统计好子数组的数目
 *
 * @Author: cookLee
 * @Date: 2025-04-16
 */
public class CountGood {

    /**
     * 主
     * \
     * 输入：nums = [1,1,1,1,1], k = 10
     * 输出：1
     * 解释：唯一的好子数组是这个数组本身。
     * \
     * 输入：nums = [3,1,4,3,2,2,4], k = 2
     * 输出：4
     * 解释：总共有 4 个不同的好子数组：
     * - [3,1,4,3,2,2] 有 2 对。
     * - [3,1,4,3,2,2,4] 有 3 对。
     * - [1,4,3,2,2,4] 有 2 对。
     * - [4,3,2,2,4] 有 2 对。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CountGood countGood = new CountGood();
        int[] nums = new int[]{3, 1, 4, 3, 2, 2, 4};
        int k = 2;
        System.out.println(countGood.countGood(nums, k));
    }

    /**
     * 双指针
     *
     * @param nums nums
     * @param k    k
     * @return long
     */
    public long countGood(int[] nums, int k) {
        int ans = 0;
        int left = 0, right = -1;
        //记录nums[i] == nums[j]的次数
        int countK = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = left; i < nums.length; i++) {
            while (countK < k && right + 1 < nums.length) {
                right++;
                countK += map.getOrDefault(nums[right], 0);
                map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            }
            //满足条件后right后面的数组都是满足条件
            if (countK >= k) {
                ans += nums.length - right;
            }
            //减少边界对应的值以及出现次数
            map.put(nums[i], map.get(nums[i]) - 1);
            countK -= map.get(nums[i]);
        }
        return ans;
    }

}
